package org.example.myleet.p1447;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> result = new ArrayList<>(n * n);
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                int gcd = gcd(i, j);
                if (gcd == 1) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(j).append('/').append(i);
                    result.add(sb.toString());
                }
            }
        }
        return result;
    }

    /**
     * Greatest Common Divisor, a should be bigger than b
     */
    public int gcd(int a, int b) {
        if (a < b) {
            return gcd(b, a);
        }
        int remainder = a % b;
        if (remainder == 0) {
            return b;
        }
        return gcd(b, remainder);
    }
}
